package link_list

// https://leetcode.cn/problems/linked-list-cycle-ii/ leetcode-142

// 数学公式推导得出来的结论，根据官方题解可知
// 快慢指针相遇时，a - c = (n -1)(b+c) ，
// 定义一个指针p从头结点出发，走完路程长度为c以后，慢指针也恰好到达入环处，再经过n-1圈之后，p指针必定和慢指针在入环处相遇
// 在写内存for循环时，先判断slow == ptr，因为此时入环处恰好是头结点
func detectCycle(head *ListNode) *ListNode {
	slow, fast, ptr := head, head, head

	for {
		if fast == nil || fast.Next == nil {
			return nil
		}

		fast = fast.Next.Next
		slow = slow.Next

		if fast == slow {

			for {
				if slow == ptr {
					return slow
				}
				slow = slow.Next
				ptr = ptr.Next
			}
		}
	}

	return nil
}
